package com.wcj.test;

import com.wcj.tree.TreeNode;

import java.util.*;

/**
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，
 * （第一层从左向右，下一层从右向左，一直这样交替）
 */
public class 按之字形顺序打印二叉树 {

    public List<List<Integer>> levelOrder(TreeNode root) {
                List<List<Integer>> res = new LinkedList<>();
                if (root == null){
                    return res;
                }
                Queue<TreeNode> queue = new ArrayDeque<>();
                queue.offer(root);
                boolean flag = true;
                while (!queue.isEmpty()){
                    Deque<Integer> list = new LinkedList<>();
                    int num = queue.size();
                    for (int i = 0;i < num;i++){
                        TreeNode poll = queue.poll();
                        if (flag){
                            list.offerLast(poll.val);
                        }else {
                            list.offerFirst(poll.val);
                        }
                        if (poll.left != null){
                            queue.offer(poll.left);
                        }
                        if (poll.right != null){
                            queue.offer(poll.right);
                        }
                    }
            flag = !flag;
            res.add(new LinkedList<Integer>(list));
        }
        return res;
    }
}
